The invention relates generally to computer graphics, and more particularly to textured range images.
In computer graphics, it is often desired to minimize the amount of geometry in a model of a scene or an object to enable efficient rendering of the model. Several effective approaches have been developed to add visual detail to low-resolution models during rendering, such as texture mapping and bump mapping, see Apodaca et al., xe2x80x9cAdvanced Renderman,xe2x80x9d Morgan Kaufmann, ISBN 1558606181, 2000.
However, there are times when low-resolution models are insufficient. For example, high-end production studios often require models with detailed explicit geometry for physical simulation, e.g., deformation and collision detection. In addition, these studios often employ sophisticated illumination that requires models with high-resolution geometry.
Displacement mapping can be applied to the low-resolution geometry of an underlying model to provide correct illumination. This is an operation that is usually performed dynamically during rendering and, therefore, precludes using the resultant model with high-resolution geometry for physical simulation. Finally, users, such as artists, designers, engineers and sculptors, may require models with high-resolution geometry in order to produce solid 3D models via 3D printing methods.
Many systems are known for direct modeling of the 3D geometry of scenes and objects. However, generating models with high-resolution geometry is a difficult and time-consuming task. It is often very hard to recreate the complexity and variety of geometric texture that occurs in nature.
High-resolution range scanners, such as Cyberware 3030, provide means for capturing existing geometry but high-resolution scanners are expensive and difficult to transport. In addition, their spatial resolution is limited. Hand-held range scanners are more portable, but they too are expensive for the casual user, and sacrifice both spatial and depth resolution for portability.
In contrast, digital cameras are portable, inexpensive, have a high spatial resolution, and are easy to use. In addition, 2D photograph editing systems such as Photoshop are dramatically simpler to use than 3D modeling systems. However, digital cameras do not provide explicit depth information.
Methods for generating the geometry for 3D models from 2D images have a significant connection to the field of computer vision. Many methods are known in the prior art for extracting shape from shade, shape from focus, and shape from stereo pairs. Szeliski, in xe2x80x9cDetermining Geometry from Imagesxe2x80x9d, SIGGRAPH 1999 Course Notes #39, Image-Based Modeling, Rendering, and Lighting, 1999, presents a bibliography and an overview of the various approaches.
Prior work has primarily focused on developing automatic techniques for acquiring an accurate global shape description of objects or scenes. In contrast, it is desired here to capture the spirit of the geometry in a scene using interactive methods by capturing fine geometric detail from a 2D image. Then, a user actively involved in the process can modify and enhance a global shape description of objects or scenes. Thus, the goal of the present invention is quite different from the goal of methods in computer vision.
Although texture synthesis methods, such as described by Efros et al., xe2x80x9cImage Quilting for Texture Synthesis and Transfer,xe2x80x9d SIGGRAPH Proceedings, pp. 341-346, 2001, can be extended to generate synthetic range images, those techniques lack xe2x80x9cdirectability.xe2x80x9d Directability is a phrase often used in the animation industry for processes that provide precise control over every detail.
The basic prior art approach known for constructing 3D models from range data is shown in FIG. 1. A range scanner 110 acquires range data 102 of a scene or object 101. Hereinafter, the term xe2x80x9cscenexe2x80x9d 101 means a natural outdoor scene, an indoor scene, or a scene that contains one or more objects, or combinations thereof. Of particular interest are highly textured scenes, for example, a rocky surface, leaves, grass, and the like, and objects with uneven and complex surface structures. The range data 102 can be processed 120 to form range images 103 and range 3D surfaces 104. A method for reconstructing the geometry 130 is used to generate a 3D model 105 from the range images 103 and range surfaces 104.
There are many reconstruction methods in the prior art. A review of these methods is described by Curless, xe2x80x9cFrom range scans to 3D modelsxe2x80x9d, Computer Graphics, Volume 33, No. 4, 1999. Some methods first determine an implicit representation of the surface, usually in the form of a sampled distance field, and then reconstruct the 3D model as a 3D iso-surface of the implicit representation. Some methods are designed to be very general, e.g., they can accept range data in the form of an unorganized cloud of surface points. Other methods use range data that are available in the form of range images, where range measurements are acquired in a regularly sampled 2D grid.
There are several methods for reconstructing 3D models from range data that make use of distance fields. Some of these methods make the general assumption that data are available only as an unorganized set of surface points. Hoppe et al., in xe2x80x9cSurface Reconstruction from Unorganized Points,xe2x80x9d Proceedings SIGGRAPH""92, pp. 71-78, 1992, generates a regularly sampled signed distance volume by defining local tangential planes from neighborhoods of scanned surface points and computing signed distances to these planes. Marching Cubes, described by Lorensen et al., in xe2x80x9cMarching Cubes: a High Resolution 3D Surface Reconstruction Algorithm,xe2x80x9d Proceedings SIGGRAPH""87, pp. 163-169, 1987, is then used to generate a surface model from the volume representation.
Bajaj et al. in xe2x80x9cAutomatic Reconstruction of Surfaces and Scalar Fields from 3D Scans,xe2x80x9d Proceedings SIGGRAPH""95, pp. 109-118, 1995, and Boissonnat et al., in xe2x80x9cSmooth Surface Reconstruction via Natural Neighbor Interpolation of Distance Functions,xe2x80x9d in Proceedings of the 16th Annual ACM Symposium on Computational Geometry, pp. 223-232, 2000, build Voronoi diagrams from scanned surface points. Then, they use the Voronoi diagram to efficiently evaluate closest distances to the surface and to define surface patches for the model. Carr et al., in xe2x80x9cReconstruction and Representation of 3D Objects with Radial Basis Functionsxe2x80x9d, Proceedings SIGGRAPH2001, pp. 67-76, 2001, fit a radial basis function to a set of on-surface and off-surface points derived from scanned surface points. The on-surface points are assigned a value of zero, while off-surface points constructed from the on-surface points are assigned a value equal to their assigned distance from the surface.
All of these methods are quite general because they can be applied to a set of unorganized points. However, when range data are available in the form of range images, it is desired to determine a distance field directly from the range images.
Curless et al., in xe2x80x9cA Volumetric Method for Building Complex Models from Range Images,xe2x80x9d Proceedings SIGGRAPH""96, pp. 303-312, 1996, Hilton et al., in xe2x80x9cReliable Surface Reconstruction from Multiple Range Images,xe2x80x9d Proceedings of the 4th Eurographics Conference on Computer Vision, pp. 117-126, 1996, and Wheeler et al., in xe2x80x9cConsensus surfaces for Modeling 3D Objects from Multiple Range Images,xe2x80x9d Proceedings of the International Conference of Computer Vision, 1998, present methods that generate a volumetric representation of the distance field from range surfaces, which are generated by connecting nearest neighbors in the range image with triangular facets.
Those methods avoid triangulation over possible occlusions in the model surface by not connecting neighbors with significant differences in range values. That approach is conservative and avoids building surfaces over unobserved regions. However, that method can lead to holes in the model that must be addressed separately as described by Curless et al. Those three methods all use a weighted averaging scheme to combine distance values from multiple scans. As for the method of Hoppe et al., those methods use Marching Cubes to generate a triangle model from the volume representation.
Curless et al. use line-of-sight distances and only compute distances in a limited shell surrounding the surface. The distance volume is run-length-encoded to reduce storage and processing times. Hilton et al. determine Euclidean distances from range surfaces in a limited shell surrounding the surface, and store the results in a regularly sampled volume. Wheeler et al. also determine Euclidean distances from range surfaces, but limit distance evaluations to the vertices of a three-color octree.
Whitaker, in xe2x80x9cA Level-Set Approach to 3D Reconstruction from Range Data,xe2x80x9d the International Journal of Computer Vision, pp. 203-231, 1998, determines line-of-sight distances directly from range images and combines distance values from multiple scans using a windowed, weighted average. Then, he uses level set methods to reduce scanner noise by evolving a surface subject to forces that attract the surface to the zero-valued iso-surface of the distance field, and satisfy a shape prior such as surface smoothness. Zhao et al., in xe2x80x9cFast Surface Reconstruction using the Level Set Method,xe2x80x9d Proceedings 1st IEEE Workshop on Variational and Level Set Methods, pp. 194-202, 1998, use a method similar to Whitaker, but initialize the distance field used to attract the evolving surface from a set of unorganized points.
Recently Perry et al. in xe2x80x9cKizamu: A System for Sculpting Digital Characters,xe2x80x9d Proceedings SIGGRAPH 2001, pp. 47-56, 2001 and Sagawa et al., in xe2x80x9cRobust and Adaptive Integration of Multiple Range Images with Photometric Attributes,xe2x80x9d Proceedings IEEE Computer Society Conference on Computer Vision and Pattern Recognition, volume 2, pp. 172-179, 2001, describe methods similar to the method of Wheeler et al., but use adaptively sampled distance fields (ADFs) instead of a three-color octree to reduce the number of distance evaluations required.
ADFs adaptively sample a distance field of a scene or object and store the sample values in a spatial hierarchy, e.g., an octree, for fast processing, see Frisken et al. xe2x80x9cAdaptively sampled distance fields: a general representation of shape for computer graphics,xe2x80x9d Proceedings SIGGRAPH 2000, pp.249-254, 2000. ADFs are memory efficient and detail directed, thus permitting very complex objects to be manipulated on desktop machines. In addition, ADFs are a volumetric representation that can be used to build upon volumetric approaches for reconstructing geometry from range data.
ADFs are described in detail in U.S. patent application Ser. No. 09/370,091, xe2x80x9cDetail directed hierarchical distance fields,xe2x80x9d filed by Frisken at al. on Aug. 6, 1999, incorporated herein by reference. ADF models generated using the present invention can be incorporated into an existing ADF sculpting system that provides an intuitive interface for manually editing the generated ADF, see U.S. patent application Ser. No. 09/810,261, xe2x80x9cSystem and method for sculpting digital models,xe2x80x9d filed by Perry et al., on Mar. 16, 2001, incorporated herein by reference, and for creating level-of-detail (LOD) triangle models from the ADF, see U.S. patent application Ser. No. 09/810,830, xe2x80x9cConversion of adaptively sampled distance fields to triangles,xe2x80x9d filed by Frisken et al., on Mar. 16, 2001, incorporated herein by reference.
There also exist several methods for generating 3D models from height fields or elevation maps that are related to the reconstruction of geometry from a single range image, H. Hoppe, xe2x80x9cSmooth View-Dependent Level-of-Detail Control and its Application to Terrain Rendering,xe2x80x9d IEEE Visualization, pp. 35-42, October, 1998. Those methods are focused on providing efficient rendering and effective visualization, but not towards subsequent editing, as desired here.
Therefore, it is desired to combine the advantages of inexpensive digital cameras and 2D editing systems to provide a simple, fast, and cost-effective method for generating the geometry and detailed texture for 3D models directly from 2D images.
It is an object of the invention to provide a method for acquiring textured range images from 2D photographs.
It is also an object of the invention to provide a method for computing distances from range images in order to convert the textured range images interactively to 3D models.
It is also an object of the invention to provide an interactive method for acquiring detailed geometry and texture for 3D models using a digital camera and a 2D image editor.
Although these methods can be worked alone, e.g., the textured range image produced by the interaction method can be converted to 3D models by reconstruction methods that use other means to compute distances, the combination of the methods provides a means for generating detailed 3D models that is cost-effective, (e.g., by using inexpensive digital cameras and significantly reducing labor), practical, (e.g., cameras can go many places range scanners cannot), approachable, (e.g., cameras and 2D editors are simple to use, while range scanners and 3D modelers are not), robust (e.g., hole-free, water-tight models are produced), and efficient (e.g., model generation takes seconds on a desktop machine).
Therefore, the invention provides a method to construct the geometry and surface texture of 3D models from range images. More specifically, the range image can be highly textured. The method can be applied to a single image or multiple images. The method is fast and memory efficient, and provides water-tight, hole-free models, which can be trivially sculpted in 3D to repair occluded regions.
The invention also provides an interactive method for generating 3D models from images acquired by an inexpensive digital camera. The method generates textured range images from photographs. The textured range images can be used, with a construction process, as a simple and effective way to generate the geometry and texture of models with exquisite detail.
These two methods can be combined with a 3D digital sculpting system to provide a powerful new design approach for generating and editing detailed 3D models.
More particularly, a textured range image is generated by first acquiring a first image of a scene illuminated with ambient light, and acquiring a second image of the scene illuminated with direct light. The first and second images are combined to determine the textured range image.